package com.example.demo.sort;

import javax.sound.midi.Soundbank;
import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        //int[] arr = {13, 56, 34, 12, 3, 69, 91, 35};
//        bubbleSortOpt(arr);
//        System.out.println(Arrays.toString(arr));

//        quickSort(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));

        int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        //shellSort(a);
        //insetSort(a);
        //selectSort(a);

        int temp[]=new int[a.length];
        mergeSort(a,0,a.length-1,temp);
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(temp));

    }



    /**
     * 冒泡
     *
     * @param arr
     */
    public static void bubbleSortOpt(int[] arr) {
        int tmp = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

    /**
     * 快速排序-获取一个中间值，分左右两边排序
     *
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int lower = getMiddle(arr, start, end);
            quickSort(arr, start, lower);
            quickSort(arr, lower + 1, end);
        }
    }

    private static int getMiddle(int[] arr, int lower, int higher) {
        int tem = arr[lower];
        while (lower < higher) {
            while (lower < higher && tem < arr[higher]) {
                higher--;
            }
            arr[lower] = arr[higher];
            while (lower < higher && tem > arr[lower]) {
                lower++;
            }
            arr[higher] = arr[lower];
        }
        arr[lower] = tem;
        return lower;
    }


    /**
     * 插入
     *
     * @param arr
     */
    public static void insetSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int insertValue = arr[i];
            int insetIndex = i - 1;
            while (insetIndex >= 0 && insertValue < arr[insetIndex]) {
                arr[insetIndex + 1] = arr[insetIndex];
                insetIndex--;
            }
            arr[insetIndex + 1] = insertValue;
        }
    }

    /**
     * ShellSort
     * gap
     * i = gap
     * i-gap ,j- gap
     */
    public static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j = j - gap) {
                    if(arr[j] > arr[j+gap]){
                        int tem = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap]=tem;
                    }
                }
            }
        }
    }


    /**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int index = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[index]){
                    index = j;
                }
            }
            int tem = arr[index];
            arr[index] = arr[i];
            arr[i] = tem;
        }
    }

    /**
     * 归并排序
     * @param arr
     * @param left
     * @param right
     * @param temp
     */
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if(left < right){
            int middle = (left + right) / 2;
            mergeSort(arr,left, middle,temp);
            mergeSort(arr,middle+1,right,temp);
            merge(arr,left,right,middle,temp);
        }
    }

    private static void merge(int[] arr, int left, int right, int middle, int[] temp) {
        int i=left;
        int j = middle+1;
        int index = 0;
        while (i <= middle && j <= right){
            if(arr[i] <= arr[j]){
                temp[index] = arr[i];
                index++;
                i++;
            }else{
                temp[index] = arr[j];
                index++;
                j++;
            }
        }

        while (i <= middle){
            temp[index] = arr[i];
            index++;
            i++;
        }
        while (j <= right){
            temp[index] = arr[j];
            index++;
            j++;
        }

        index=0;
        int tempLeft=left;
        while (tempLeft<=right) {
            arr[tempLeft]=temp[index];
            index++;
            tempLeft++;
        }
    }





}
